package com.taijia.chapter5;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Count3Quit {

	/**
	 * 通过数组计算
	 * @param persons
	 * @return
	 */
	private static int calculate(boolean[] persons) {
		int leftCount = persons.length, index = 0, counter = 0;
		while (leftCount>1) {
			if (persons[index] == true) {
				counter++;
				if (counter == 3) {
					persons[index] = false;
					counter = 0;// this node is 0, next node is 1, current node is 0
					leftCount--;
				}
			}
			index++;
			if (index == persons.length) {
				index = 0;
			}
		}
		for(int i=0;i<persons.length;i++) {
			if(persons[i]) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 通过List计算
	 * @param persons
	 * @return
	 */
	private static int calculate(List<Integer> persons) {
		int count = 0, index = 0;
		while (persons.size() > 1) {
			count++;
			if (count == 3) {
				persons.remove(index);
				count = 1;//this node is removed, next node is 1, current node is 1
			}
			index++;
			if (index >= persons.size()) {
				index = (index - persons.size());
			}
		}
		return persons.get(0);
	}
	
	private static int calculate(LinkedList<Integer> persons) {
		while(persons.size()>1) {
			
		}
		return persons.get(0);
	}

	public static void main(String[] args) {
		final int SIZE = 500;
		boolean[] persons = new boolean[SIZE];
		for (int i = 0; i < SIZE; i++) {
			persons[i] = true;
		}
		System.out.println(calculate(persons));
		System.out.println();
		List<Integer> personsList = new ArrayList<Integer>();
		for (int i = 0; i < SIZE; i++) {
			personsList.add(i);
		}
		System.out.println(calculate(personsList));
	}
}
